package structure;

import java.util.*;

public class Main10 {
    public static void main(String[] args) {

    }
    //动态规划解"爬楼梯问题"
    public static int climbStairs(int num){
        if(num == 0){
            return 0;
        }
        if(num == 1){
            return 1;
        }
        if(num == 2){
            return 2;
        }
        int a = 1;
        int b = 2;
        int temp = 0;
        for(int i = 3;i <= num;i++){
            temp = a + b;
            a = b;
            b = temp;
        }
        return temp;
    }
    //力扣20.有效的括号
    class Solution1 {
        public boolean isValid(String s) {
            Stack<Character> stack = new Stack<>();
            char[] str = s.toCharArray();
            char a = str[0];
            if (a == ')' || a == ']' || a == '}' || str.length % 2 != 0) {
                return false;
            }
            for (int i = 0; i < str.length; i++) {
                if (doString(str[i])) {
                    a = str[i];
                    stack.push(str[i]);
                } else {
                    if ((a == '(' && str[i] != ')') || (a == '[' && str[i] != ']') || (a == '{' && str[i] != '}')) {
                        return false;
                    } else {
                        if (stack.empty()) {
                            return false;
                        }
                        stack.pop();
                        if (!stack.empty()) {
                            a = stack.peek();
                        }
                    }
                }
            }
            if (!stack.empty()) {
                return false;
            }
            return true;
        }

        public boolean doString(char c) {
            String s = String.valueOf(c);
            if (s.equals("(") || s.equals("[") || s.equals("{")) {
                return true;
            }
            return false;
        }
    }

    //力扣150.逆波兰表达式求值
    class Solution0 {
        public int evalRPN(String[] tokens) {
            Stack<Integer> stack = new Stack<>();
            for (int i = 0; i < tokens.length; i++) {
                String s = tokens[i];
                if (!doNum(s)) {
                    stack.push(Integer.valueOf(s));
                } else {
                    int a = stack.pop();
                    int b = stack.pop();
                    switch (s) {
                        case "+":
                            stack.push(b + a);
                            break;
                        case "-":
                            stack.push(b - a);
                            break;
                        case "*":
                            stack.push(b * a);
                            break;
                        case "/":
                            stack.push(b / a);
                            break;
                    }
                }
            }
            return stack.pop();
        }
        public boolean doNum(String s) {
            if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
                return true;
            }
            return false;
        }
    }
}

